// 摆动排序 II
// Created by madison on 2022/11/17.
//


#include "vector"

using namespace std;

class Solution {
public:
    // 方法一：排序
    void wiggleSort(vector<int> &nums) {
        int n = nums.size();
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        int x = (n + 1) / 2;
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
            nums[i] = arr[j];
            if (i + 1 < n) {
                nums[i + 1] = arr[k];
            }
        }
    }
};

int main() {
    vector<int> nums = {1, 5, 1, 1, 6, 4};
    Solution solution;
    solution.wiggleSort(nums);
    for (int i = 0; i < nums.size(); ++i) {
        printf("%d\t", nums[i]);
    }
    return 0;
}